home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / incl / LEDA / b_node_pq.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  1.4 KB  |  74 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  b_node_pq.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef LEDA_B_NODE_PQ_H
  17. #define LEDA_B_NODE_PQ_H
  18.  
  19.  
  20. //------------------------------------------------------------------------------
  21. // bounded node priority queue
  22. //
  23. // S. Naeher (1993)
  24. //------------------------------------------------------------------------------
  25.  
  26.  
  27. template <int DELTA> 
  28. class b_node_pq 
  29. {
  30.   node_list bucket[DELTA+1];
  31.  
  32.   node_struct stop_item;
  33.   node_list*  stop;
  34.   node_list*  minptr;  // pointer to bucket of nodes with minimal dist value
  35.   int         val0;    // current dist value of nodes in bucket[0]
  36.  
  37.   node nil_node;       // node to be returned by del_min if queue is empty
  38.  
  39.  
  40. public:
  41.  
  42. b_node_pq(node v = nil)
  43. { minptr = bucket; 
  44.   stop = bucket+DELTA; 
  45.   val0 = 0; 
  46.   stop->append(&stop_item);
  47.   nil_node = v;
  48.  }
  49.  
  50. node del_min()
  51. { while (minptr->empty()) minptr++;
  52.  
  53.   if (minptr == stop) 
  54.   { val0 += DELTA;
  55.     minptr = bucket;
  56.     while (minptr->empty()) minptr++;
  57.    }
  58.  
  59.   return (minptr==stop) ? nil_node : minptr->pop();
  60.  }
  61.  
  62.  
  63. void insert(node w, int d) 
  64. { if ((d-=val0) >= DELTA) d -= DELTA;
  65.   bucket[d].push(w); 
  66.  }
  67.  
  68. void del(node w) { node_list::del_node(w); }
  69.  
  70.  
  71. };
  72.  
  73. #endif
  74.